# -*- coding: utf-8 -*-
# @Time    : 2021/1/2 下午12:17
# @Author  : tgy
# https://leetcode-cn.com/problems/partition-list/

class Solution:

    def numDecodings(self, s:str) -> int:
        ...
        s_len = len(s)
        """
         dp[i] = d[i - 1] + dp[i - 2]
        """
        one = 1
        two = 0 if s[0] == '0' else 1
        for i in range(2, s_len + 1):
            ...
            sum = 0
            if s[i - 1] != '0':
                sum += two
            if s[i - 2] == '1' or (s[i - 2] == '2' and s[i - 1] <= '6'):
                sum += one
            one = two
            two = sum

        return two

    def numDecodings01(self, s: str) -> int:
        ...
        self.count = 0

        self.doNumDecodings(s, 0)
        return self.count

    def doNumDecodings(self, s: str, index):
        ...
        if index >= len(s):
            self.count += 1
            print(self.count)
            return

        letter = s[index]
        if letter != '0':
            self.doNumDecodings(s, index + 1)

        if index + 1 >= len(s):
            return

        if s[index] == '1' or (s[index] == '2' and s[index + 1] <= '6'):
            self.doNumDecodings(s, index + 2)

if __name__ == '__main__':
    ...
    solution = Solution()
    print(solution.numDecodings("112"))